package com.huanyu.backend.study.datastructure.queue;

import java.util.AbstractCollection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;

/**
 *
 * 自定义简单队列的实现
 * 尾插头取实现先入先出
 * 跟生活的排队付钱时类似
 * @author arron
 */
public class SimpleQueue<T> extends AbstractCollection<T> implements Queue<T> {

    private Node<T> head;
    private Node<T> tail;
    private int size;

    /**
     * 静态内部类的使用原则总结：
     * @param <T>
     */
    private static class Node<T> {
        T data;
        Node<T> pre;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    public SimpleQueue() {
        this.head = new Node<>(null);
        this.tail = new Node<>(null);
        head.next = tail;
        tail.pre = head;
        this.size = 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new QueueIterator();
    }

    @Override
    public int size() {
        return size;
    }

    /**
     * 使用双向链表要注意链表节点的next和pre都要赋值，不然可能会形成无效环路
     * @param t
     * @return
     */
    @Override
    public boolean add(T t) {
        if (size > Integer.MAX_VALUE - 1) {
            throw new IllegalStateException();
        }

        Node<T> preNode = tail.pre;
        Node<T> node = new Node<>(t);
        preNode.next = node;
        node.pre = preNode;
        node.next = tail;
        tail.pre = node;
        size++;
        return true;
    }

    @Override
    public boolean offer(T t) {
        if (size > Integer.MAX_VALUE - 1) {
            return false;
        }
        return add(t);
    }

    @Override
    public T remove() {
        if (size == 0) {
            throw new NoSuchElementException();
        }

        Node<T> nextNode = head.next;
        head.next = nextNode.next;
        nextNode.next.pre = head;
        size--;
        nextNode.next = null;
        nextNode.pre = null;
        T data = nextNode.data;
        nextNode.data = null;
        return data;
    }

    @Override
    public T poll() {
        if (size == 0) {
            return null;
        }
        return remove();
    }

    @Override
    public T element() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
        return peek();
    }

    @Override
    public T peek() {
        return head.next.data;
    }

    public class QueueIterator implements Iterator<T> {
        private Integer iteratorIndex = 0;

        @Override
        public boolean hasNext() {
            return size > iteratorIndex;
        }

        @Override
        public T next() {
            iteratorIndex++;
            Node<T> next = head;
            for (int i = 0; i < iteratorIndex; i++) {
                next = next.next;
            }
            return next.data;
        }
    }
}
